


// 打印结构体 需要引入Debug特征，否则就要自己实现fmt方法
#[derive(PartialEq, Eq, Clone, Debug)]
 // 链表节点
pub struct ListNode{
    pub val:i32,
    pub next:Option<Box<ListNode>>, // Box表示智能指针，在堆上分配内存
}


impl ListNode{
    #[inline]
    pub fn new(val: i32) ->Self{
        ListNode{next:None, val}
    }
 
    pub fn  print(&mut self)
    {
        let mut current =  &mut self.next;

        println!("{}", self.val);

        // 新建一个临时节点，取得该头结点的引用
        while let Some(ref mut node) = current {
            
            println!("{:#?},",node.val);

            if node.next.is_none(){
                break;
            }else {
                current = &mut node.next;
            }
            
        }

    }

}



// 链表头
pub struct LinkedList{
    pub head:Option<Box<ListNode>>,
}

 impl LinkedList{

    pub fn new() -> Self{
        LinkedList{head: None}
    }

    pub fn append(&mut self, val:i32){
        // 在堆上开辟空间
        let new_node = Box::new(ListNode::new(val));

        // 判断对象当前链表是否为空
        if self.head.is_none(){
            self.head = Some(new_node);
        }
        else {
            // 取对象的头结点的引用
            let mut current = &mut self.head;

            // 新建一个临时节点，取得该头结点的引用
            while let Some(ref mut node) = current {
                // 如果该节点的next节点为空，则插入新节点
                if node.next.is_none(){
                    node.next = Some(new_node);
                    break;
                }
                // 否则 移动current到下一个节点
                current = &mut node.next;
            }
        }

    }

    pub fn delte_value(&mut self, value: i32) -> bool
    {
        match self.head {

            // 1、当链表只有一个节点，且节点值相等，则进入该分支
            Some(ref mut head_node) if head_node.val == value => {
                self.head = head_node.next.take();
                println!("the list is only one node");
                true
            }

            // 2、链表为空
            None =>  {
                println!("the list node is None"); 
                false
            }

            // 3、当链表节点数量不止一个，开始遍历
            _ => {

                // 建立一个前向节点
                let mut prev = &mut self.head;

                // 建立一个当前节点，用clone克隆一份prev的值，并指向prev的下一个节点
                let mut new_cur = &mut prev.clone();
                new_cur = &mut new_cur.as_mut().unwrap().next;

                while new_cur.is_some(){
                    // 取new_cur 的next字段的可变引用，并更新 new_cur
                    if new_cur.as_mut().unwrap().val == value{
        
                        // unwrap 是从 Option中拿出值，如果值为None，则panic，这里用，是要求这里必须要有值，否则就崩溃
                        // 前一个节点的next 指向 当前节点的下一个。删除当前节点。
                        prev.as_mut().unwrap().next = new_cur.as_mut().unwrap().next.clone();

                        return true;
                    }
                    new_cur = &mut new_cur.as_mut().unwrap().next;
                    prev = &mut prev.as_mut().unwrap().next;
                }
                return  false;
            }
        }

    }

    pub fn print(&mut self){

        let mut current = &mut self.head;

        // 新建一个临时节点，取得该头结点的引用
        while let Some(ref mut node) = current {
            
            println!("{:#?},",node.val);

            if node.next.is_none(){
                break;
            }else {
                current = &mut node.next;
            }
            
        }
    }

}





pub struct  Solution;

impl Solution{
    // 代码：12-15
    pub fn reverse_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> 
    {
        // 创建两个节点
        let mut prev = None;
        let mut curr = head;

        // 从curr中取出节点送入循环处理，直到take到None结束，取出的节点用Some把其中封装的值取出。
        while let Some(mut curr_node) = curr.take() 
        {
            // 取出的节点 放在curr_node，保存该节点的下一个节点
            let next_temp = curr_node.next.take();

            // 把当前节点的下一个节点指向 prev节点
            curr_node.next = prev.take();

            /*
                将prev 指向当前节点的位置，
                这里curr_node 类型是 Box<ListNode>，赋值给prev需要用Some包裹
             */
            prev = Some(curr_node);

            /* 把刚刚保存的 当前节点的下一个节点，赋值给curr节点 ，这样两个节点就整体后移*/
            curr = next_temp;
        }

        prev

    }

    // 代码 12-16
    pub fn middle_node(head: Option<Box<ListNode>>) -> Option<Box<ListNode>>
    {
        let mut fast_p = &head;
        let mut slow_p = &head;

        while fast_p.is_some() && fast_p.as_ref().unwrap().next.is_some() {
            
            // slow_p 向后移动一个节点，这里 as_ref 是将值 转换为值的 静态引用:
            // Option<T> --> Option<&T>
            // 将值转换为 引用，并找到下一个节点
            slow_p = &slow_p.as_ref().unwrap().next;

            // fast_p 向后移动两个节点
            fast_p = & fast_p.as_ref().unwrap().next.as_ref().unwrap().next;

        }

        // Option<Box<ListNode>> 需要引入clone特征
        slow_p.clone()
        
    }

    // 代码 12-17
    pub fn merge_two_lists(
            list_node1: Option<Box<ListNode>>,
            list_node2: Option<Box<ListNode>>
    ) -> Option<Box<ListNode>>
    {
        match (list_node1, list_node2) {

            (Some(node1), None) => Some(node1),
            (None, Some(node2)) => Some(node2),
            (Some(mut node1), Some(mut node2)) => {
                if node1.val < node2.val {
                    let n = node1.next.take();
                    node1.next = Solution::merge_two_lists(n, Some(node2));

                    Some(node1)
                }
                else {
                    let n = node2.next.take();
                    node2.next = Solution::merge_two_lists(Some(node1), n);

                    Some(node2)
                }
            }
            _ => None,
        }
    }

    pub fn remove_nth_from_end(head: Option<Box<ListNode>>, n: i32) -> Option<Box<ListNode>>
    {
        // 创建一个哑节点，用于指向原来链表表头
        let mut dummy = Some(Box::new(ListNode{val: 0, next: head}));
       
        // 创建一个指向dummy的可变引用，可以用于修改dummy的next字段，且可以保持dummy作为表头的稳定性。
        // 类似一个灵活的指针，指向后边的节点
        let mut cur: &mut Option<Box<ListNode>> = &mut dummy;
        let mut length = 0;

        // cur.as_mut 将cur的类型（&mut Option<Box<ListNode>> ）转换为 Option<&mut Box<ListNode>>
        // 然后模式匹配 Some(node) 来获得node的可变引用（&mut Box<>）。
        while let Some(node) = cur.as_mut() {
            cur = &mut node.next;
            if let Some(_node) = cur{
                length += 1;
            }
        }

        // 为 Option中的 T 的值 取可变引用： Option<T> -> Option<&mut T>
        let mut new_cur = dummy.as_mut();

        let idx = length -n;
        for _ in 0..idx{
            // 取new_cur 的next字段的可变引用，并更新 new_cur
            new_cur = new_cur.unwrap().next.as_mut();
        }

        // 删掉第n个节点， 保存下下个节点地址： 取当前节点的可变引用，然后取出Some(T)的T的下一个节点的下一个节点
        let next = 
            new_cur.as_mut().unwrap().next.as_mut().unwrap().next.take();

        new_cur.as_mut().unwrap().next = next;

        dummy.unwrap().next

    }

    pub fn remove_nth_from_end_nb(head: Option<Box<ListNode>>, n: i32) -> Option<Box<ListNode>>
    {
        let mut dummy = Some(Box::new(ListNode{val: 0, next: head}));
        let mut slow_p = &mut dummy;
        let mut fast_p = &mut slow_p.clone();

        // fast向后移动n+1个节点，让快慢指针之间相隔n个节点。
        for _ in 1..=n+1{
            fast_p = &mut fast_p.as_mut().unwrap().next;
        }

        while fast_p.is_some() {
            fast_p = &mut fast_p.as_mut().unwrap().next;
            slow_p = &mut slow_p.as_mut().unwrap().next;
        }

        let next = &slow_p.as_mut().unwrap().next.as_mut().unwrap().next;
        slow_p.as_mut().unwrap().next = next.clone();

        dummy.unwrap().next
    }

 

}


#[cfg(test)]
mod list_node{
    use super::{LinkedList, Solution};

    // 翻转链表
    #[test]
    fn reserve_list()
    {
        let mut link_list = LinkedList::new();
       

        link_list.append(1);
        link_list.append(2);
        link_list.append(3);
        link_list.append(4);

        link_list.print();

        let res = link_list.delte_value(2);
        println!("{},,,",res);
        link_list.print();

     let list_resver =  Solution::reverse_list(link_list.head);
     
     println!("{:#?}",list_resver);
    
    }


    #[test]
    // 取链表中间的值
    fn middle_list()
    {
        let mut link_list = LinkedList::new();
    
        link_list.append(1);
        link_list.append(2);
        link_list.append(3);
        link_list.append(4);

        let list_resver =  Solution::middle_node(link_list.head);
        
        println!("{:#?}",list_resver);
    }


    #[test]
    // 合并两个有序链表
    fn merge_list()
    {
        let mut link_list1 = LinkedList::new();
    
        link_list1.append(1);
        link_list1.append(2);
        link_list1.append(3);
        link_list1.append(4);

        let mut link_list2 = LinkedList::new();
    
        link_list2.append(5);
        link_list2.append(7);
        link_list2.append(8);
        link_list2.append(9);

        let mut list =  Solution::merge_two_lists(link_list1.head, link_list2.head);
        
        list.take().unwrap().print();

       // println!("{:#?}",list_resver);
    }

    #[test]
    // 删除链表中倒数第n个节点
    fn remove_nth_node_test1()
    {
        let mut link_list1 = LinkedList::new();
    
        link_list1.append(1);
        link_list1.append(2);
        link_list1.append(3);
        link_list1.append(4);


        let mut list =  
            Solution::remove_nth_from_end(link_list1.head, 2);
        
        list.take().unwrap().print();
    }

    #[test]
    // 删除链表中倒数第n个节点
    fn remove_nth_node_test_nb()
    {
        let mut link_list1 = LinkedList::new();
    
        link_list1.append(1);
        link_list1.append(2);
        link_list1.append(3);
        link_list1.append(4);


        let mut list =  
            Solution::remove_nth_from_end_nb(link_list1.head, 2);
        
        list.take().unwrap().print();
    }

    

}

